[10 bodů] Dokažte následující vztah (výpočtem nebo kombinatorickou úvahou nebo nějak jinak), pro n≥1n \geq 1n≥1:
∑k=0nk⋅(nk)=n⋅2n−1
\sum_{k=0}^{n}k \cdot \binom{n}{k} = n \cdot 2^{n-1}
k=0∑nk⋅(kn)=n⋅2n−1
(a) [2 body] Doplňte definici symetrické relace:
Řekneme, že relace RRR na množině XXX je symetrická, pokud…
(b) [3 body] Nechť RRR je relace {(1,1),(2,2),(2,3),(3,2)}\{(1, 1), (2, 2), (2, 3), (3, 2)\}{(1,1),(2,2),(2,3),(3,2)} na množině X={1,2,3}X = \{1, 2, 3\}X={1,2,3}.
Je RRR reflexivní relace? Je RRR symetrická relace? Odpovědi dostatečně zdůvodněte.
(c) Nyní nechť Y={1,2,3,4}Y = \{1, 2, 3, 4\}Y={1,2,3,4}
i. [4 body] Kolik je všech ekvivalencí na množině YYY? (Nápověda: Ekvivalence nám dělí nosnou množinu na třídy ekvivalence.)
ii. [2 body] Kolik je všech relací na množině YYY?
iii. [3 body] Kolik je reflexivních relací na množině YYY? (Nápověda: Jak vypadá matice, která odpovídá reflexivní relaci?)
[10 bodů] Dokažte dolní a horní mez tohoto odhadu:
nn/2≤n!≤(n+12)n
n^{n/2} \leq n! \leq \left( \frac{n+1}{2} \right)^n
nn/2≤n!≤(2n+1)n
(a) [4 body] Formulujte Kuratowského větu.* Stačí formulace, větu nedokazujte.
(b) [4 body] Je graf na obrázku rovinný? Buďto ho nakreslete rovinně, nebo nějakým přesvědčivým (!) způsobem argumentujte, proč rovinné nakreslení neexistuje.
(c) [4 body] Průměrný stupeň grafu GGG je průměr jeho stupňů, neboli číslo
1n(∑v∈V(G)deg(v))
\frac{1}{n} \left( \sum_{v \in V(G)}\text{deg}(v) \right)
n1v∈V(G)∑deg(v)
(kde $njepocˇetvrcholu˚grafu je počet vrcholů grafu jepocˇetvrcholu˚grafuG$). Je pravdivé následující tvrzení? Buďto ho dokažte (třeba s použitím nějaké věty z přednášky), nebo najděte nějaký konkrétní protipříklad.
Tvrzení: *Kdykoliv GGG je graf, který má průměrný stupeň nejvýše 2,32,32,3, pak je GGG rovinný.
(a) [4 body] Doplňte definice grafu a souvislého grafu:
(b) Pokud ttt je přirozené číslo a t≥2t \geq 2t≥2, tak definujeme graf GtG_tGt takto: vrcholy jsou všechny dvouprvkové množiny čísel z množiny {1,…,t}\{1, \ldots, t\}{1,…,t} (neboli V(Gt)=({1,…,t}2)V(G_t) = \binom{\{1, \ldots, t\}}{2}V(Gt)=(2{1,…,t})) a dvě takové množiny tvoří hranu právě tehdy, když jsou disjunktní. Zde je například obrázek G5G_5G5:
(Mimochodem, tyto grafy jsou celkem důležité a mají název: Kneserovy grafy.)
[4 body] Pro každé t≥2t \geq 2t≥2 rozhodněte, zda je GtG_tGt souvislý graf. Odpověď dostatečně zdůvodněte.
(c) [3 body] Graf GtG_tGt definovaný výše má všechny vrcholy stejného stupně. Jakého? (Bude to pochopitelně nějaké číslo, které závisí na ttt.) Odpověď dostatečně zdůvodněte.
(d) [3 body] Nyní předpokládejme, že t=4k+3t = 4k+3t=4k+3 pro nějaké přirozené číslo kkk. Je graf GtG_tGt (definovaný výše) eulerovský? Odpověď dostatečně zdůvodněte.
